package leetcode.editor.cn1;

import com.leetcode.entity.TreeNode;

public class BalancedTree {

    public static void main(String[] args) {
        Solution solution = new BalancedTree().new Solution();

        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
//        root.right.left.left = new TreeNode(7);
//        root.right.left.left.left = new TreeNode(7);
        System.out.println(solution.isBalanced(root));
    }

    class Solution {

        public boolean isBalanced(TreeNode root) {
            return depth(root) != -1;
        }

        public int depth(TreeNode node) {
            if (node == null)
                return 0;
            int leftDepth = depth(node.left);
            if (leftDepth == -1)
                return -1;
            int rightDepth = depth(node.right);
            if (rightDepth == -1)
                return -1;
            if (Math.abs(leftDepth - rightDepth) >= 2)
                return -1;
            return 1 + Math.max(leftDepth, rightDepth);
        }
    }
}
